package algorithm.hashtable;

import java.util.HashMap;
import java.util.Map;

/**
 * leetcode : https://leetcode.com/problems/isomorphic-strings/description/
 * 205. Isomorphic Strings
 * Difficulty : Easy
 *
 * 判断俩字符串是不是同构字符串
 * 举栗：
 * Input: s = "egg", t = "add"
 * Output: true
 *
 * Input: s = "foo", t = "bar"
 * Output: false
 *
 * @Author Antony
 * @Since 2018/7/28 1:03
 */
public class IsomorphicStrings {

    public static void main(String[] args) {
        String s1 = "eggs";
        String s2 = "addd";
        System.out.println(isIsomorphic(s1, s2));
    }

    public static boolean isIsomorphic(String s, String t) {

        return true;
    }


    /**
     * beats 65.57% - 9ms
     * 时间复杂度: O(N)
     * 空间复杂度: O(1) 实际使用一个Map
     *
     * 思路：
     * Map的key 和 val 分别对应s和t中的char
     * 如果key存在，那判断取到的val 是否和 t对应的char相等，如果不等则返回fals
     * 如果key不存在，那判断val是否存在，如果不存在，就执行put(key,val)
     * 还有其他情况，那就返回false
     * 全部遍历完，那说明没有遇到false情况，返回true
     *
     * 缺陷：
     * 时间损耗主要在 containsValue上，这个时间复杂度不是O(1), 而是O(N)
     */
    public static boolean isIsomorphic_oneHashMap(String s, String t) {
        if(s.length() != t.length()) return false;
        Map<Character, Character> map = new HashMap<>();
        for(int i=0; i<s.length(); i++){
            char key = s.charAt(i);
            char val = t.charAt(i);
            if(map.containsKey(key)){
                if(val != map.get(key)) return false;
            }else if(!map.containsValue(val)){
                map.put(key, val);
            }else{
                return false;
            }
        }

        return true;
    }


    /**
     * beats 11.95% - 21ms
     *
     * 时间复杂度:O(N)
     * 空间复杂度:O(1) 实际情况是两个Map，每个Map最大也就26个（全部英文字母都出现）
     *
     * 思路：
     * 两个Map key=char val=int
     * key记录遇到过的char，val记录一共有几个不同的char
     * 如果是同构的，只有两种情况：
     * 1）get的结果都是null, 那么incr自增，往两个map中put进去
     * 2）get的结果都不是null，那么这个两个结果的值必定相等。
     *
     * 其他的情况就直返回false。
     * 如果遍历完了还没有返回false，那就是true
     */
    public static boolean isIsomorphic_twoHashMap(String s, String t) {
        if(s.length() != t.length()) return false;
        Map<Character, Integer> sMap = new HashMap<>();
        Map<Character, Integer> tMap = new HashMap<>();
        int incr = 0;
        for(int i=0; i<s.length(); i++){
            char sChar = s.charAt(i);
            char tChar = t.charAt(i);
            Integer sIncr = sMap.get(sChar);
            Integer tIncr = tMap.get(tChar);
            if(sIncr == null && tIncr == null){
                incr++;
                sMap.put(sChar, incr);
                tMap.put(tChar, incr);
            }else if(sIncr != null && tIncr != null){
                if(!sIncr.equals(tIncr)) return false;
            }else{
                return false;
            }
        }
        return true;
    }
}
